This application relates to the following commonly assigned, concurrently filed U.S. patent application:
Ser. No. 09/203,236 invented by Charles M. Doland entitled xe2x80x9cMETHOD AND APPARATUS FOR DETECTING ALTERATIONS IN DATA MESSAGESxe2x80x9d, which is incorporated herein by reference.
The present invention relates generally to the field of message encryption and more particularly to the field of pseudo-random sequence generation for message encryption.
A wide area network such as the Internet may connect thousands of network nodes, including routers, bridges, hubs, servers, and user terminals. In transmitting a message from a sender node to a receiver node over a wide area network, security is a great concern, because messages in transmission are susceptible to interception by unintended third parties at any network node. This problem is typically addressed by encrypting a private message at the sender node prior to transmission of the message, then decrypting the message at the receiver node. Encryption refers to a process of disguising a message sent from a sender node so that an unintended third party cannot recover the meaning of the message, even if the unintended third party has intercepted the message. Decryption refers to a process of recovering an encrypted message after an intended receiver node has received the encrypted message. For a receiver to recover an encrypted message received from a sender, the sender and the receiver must both agree on a predetermined encryption and decryption system.
An encryption and decryption system can be conveniently described using the following notations, where:
(1) a plain (not encrypted) message is denoted by P;
(2) an encryption transformation function is denoted by E;
(3) an encrypted message is denoted by C, where C=E(P);
(4) a decryption transformation is denoted by D; and
(5) a decrypted message is also denoted by P, where P=D(E(P)).
Note that a decrypted message has the same notation as a plain message, because decrypting an encrypted message returns the original, unencrypted message.
To enhance security, most modern encryption systems use an encryption key, denoted by Ke, to encrypt messages prior to transmitting the messages, and a decryption key, denoted by Kd, to decrypt the messages upon receiving the messages. (The decryption key is often transmitted to the receiver node using a secure communication channel, to improve the security of the message, which can then be sent over an insecure channel.) In the available art, there are two general forms of key-based encryption and decryption systems: symmetric-key and public-key. In symmetric-key systems, the encryption key can be calculated from the decryption key and vice versa. Since in many such systems the encryption key Ke and the decryption key Kd are the same, the encryption key and the decryption key can be denoted by K. Thus, a symmetric encryption and decryption system can be described using the following notations, where:
(6) a plain message is denoted by P;
(7) a symmetric key is denoted by K;
(8) an encryption transformation is denoted by EK;
(9) an encrypted message is denoted by C, where C=EK(P);
(10) a decryption transformation is denoted by DK; and
(11) a decrypted message is also denoted by P, where P=DK(EK(P)).
A simple exemplary symmetrical transformation between a sender and a receiver is the XOR logic operation. In this transformation, the plain message is xe2x80x9cXORedxe2x80x9d bit by bit with the key to generate an encrypted message. To regenerate the message at the receiver node, the encrypted message is once again XORed with the key. This series of operations reproduces the original message. Using the XOR logic operation, a symmetric-key encryption and decryption process can be described as follows:
EK(x)=x XOR K;xe2x80x83xe2x80x83(12)
DK(x)=x XOR K;xe2x80x83xe2x80x83(13)
C=EK(P)=P XOR K;xe2x80x83xe2x80x83(14)
and
P=DK(C)=C XOR K=(P XOR K)XOR K.xe2x80x83xe2x80x83(15) 
Symmetric encryption and decryption systems are divided into two categories: stream ciphers and block ciphers. A cipher refers to a mathematical function (such as XOR) used for encryption and decryption. In a stream cipher, a message is encrypted one bit at a time. In a block cipher, a message is encrypted a block at a time.
In real world applications, encrypted messages are subject to attack, a process of recovering the encrypted messages without being informed about the encryption algorithm or the encryption key. The security of an encryption system against attack typically depends on two elements: the strength of the encryption algorithm selected and the length of the key used.
Usually, a more secure encryption algorithm is more complicated than a less secure encryption algorithm. Consequently, greater expense and time are required to attack a more secure encryption algorithm. However, often more time and computing power are also required to perform the encryption and decryption using a more secure encryption algorithm. In some commercial settings, such costs are not necessary or feasible. By way of example, a consumer may use a desktop computer at home to conduct a real-time business transaction. The consumer""s desktop computer may not have the computing power to perform a complicated encryption and decryption at such high speed. Further, if the amount of the business transaction is less than $1,000.00, an attacking cost above $1,000.00 will make the attack non-advantageous. As another example, some messages are only confidential for a short period of time, e.g., two months. A simple encryption algorithm is sufficient for such messages, if the attacking time takes more than two months. However, selecting a simple encryption algorithm leaves a user more vulnerable to attack than selecting a more complicated encryption algorithm.
The bit length of the key also affects the security of an encryption system. Any key-based encryption method is susceptible to a xe2x80x9cbrute forcexe2x80x9d attack. A brute force attack attempts to decrypt a message by applying the decryption function to the message, using each of the possible keys. To be secure against this type of attack, there must be a sufficient number of possible keys to make the attack too time-consuming to be useful. If a key is represented as a binary integer, the number of possible keys is 2n, where n is the number of bits in the key. Thus, in general, longer keys provide greater security against a brute force attack. For any given encryption method, there may be other methods of attacking or breaking the encryption, as well.
The choice between simple and complicated encryption algorithms presents a dilemma. While it is desirable to use simple encryption algorithms to suit some business transaction settings, selecting a simple encryption algorithm leaves an encrypted message vulnerable to attack. Similarly, increasing a key bit length increases the number of possible keys, thus enhancing the security of a encrypted message.
Therefore, there is a need to provide a method of encrypting messages adaptable to using a relatively simple encryption algorithm without compromising the security of encryption.
The present invention provides a novel method of generating a pseudo-random sequence of integers, and applies the method to the encryption of messages. The method uses a key K and a pair of prime numbers p and q, where q=2p+1. Specifically, a sequence of integers z(i), i=1, 2, . . . , n, is generated as follows.
y(i)=Ki mod qxe2x80x83xe2x80x83(16)
z(i)=y(i), if y(i)xe2x89xa6pxe2x80x83xe2x80x83(17)
z(i)=qxe2x88x92y(i), if y(i) greater than pxe2x80x83xe2x80x83(18)
According to a first aspect of the invention, the sequence of integers is used to generate a stream cipher. Specifically, a sequence of integers z(i) is formed according to equations (16)-(18), where i=1, 2, . . . , n. A sequence of bits b(i) is then formed from integers z(i), for example by selecting the least significant (or most significant) bit from each value z(i). The sequence of bits b(i) is then used to encrypt a message using a selected encryption algorithm such as the XOR algorithm. In another embodiment, the sequence of integers is used to encrypt the message without generating a sequence of b(i).
According to a second aspect of the invention, the pseudo-random sequence of integers is used to generate a block cipher. A sequence of bits b(i) is formed from integers z(i) as in the previously described embodiment. However, in this embodiment the sequence of bits b(i) is then used to encrypt a message by performing a bit position permutation on one or more message blocks.
According to a third aspect, the sequence of bits b(i) is used to encrypt a message by performing a bit pattern permutation on one or more message blocks.
According to a fourth aspect of the invention, a message block is divided into sub-blocks. The message block is encrypted by alternately applying a bit position permutation to the entire message block and applying a bit pattern permutation to each of the sub-blocks. In another embodiment, other (non-alternating) patterns of permutations are applied.